package linklist;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/6/10 09:57
 */
public class LeetCode_61 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode rotateRight(ListNode head, int k) {
        //0. 特殊情况
        if (head==null || head.next==null){
            return head;
        }
        //1. 计算长度
        int size =1;
        ListNode temp = head;
        while (temp.next!=null){
            size++;
            temp=temp.next;
        }
        if (k%size==0){
            return head;
        }
        head = reverse(head,1,size);
        head = reverse(head,1,k%size);
        head = reverse(head,k%size+1,size);
        return head;
    }

    private ListNode reverse(ListNode head, int i, int j) {
        //1. 添加临时头节点
        ListNode tempHead = new ListNode(0,head);
        //2. 寻找i-1节点，j节点
        ListNode preStart = findList(tempHead,i-1);
        ListNode start = preStart.next;
        ListNode aftEnd = findList(tempHead,j+1);
        //3. 定义指针
        ListNode p=start,q=p.next;
        //4. 循环
        while (q!=aftEnd){
            ListNode temp = q.next;
            q.next=p;
            p=q;
            q=temp;
        }
        //5. 修改指针
        start.next=q;
        preStart.next=p;
        return tempHead.next;
    }

    private ListNode findList(ListNode tempHead, int i) {
        int j=0;
        while (j<i){
            j++;
            tempHead=tempHead.next;
        }
        return tempHead;
    }


}
